阅读笔记：Optimized Large-Scale Road Sensing Through Crowdsourced Vehicles
一、基本信息
- 阅读人和日期：ZP Guo，2022.5.3
- 引用格式：Lai, Y., Xu, Y., Mai, D., Fan, Y., & Yang, F. (2022). Optimized Large-Scale Road Sensing Through Crowdsourced Vehicles. IEEE Transactions on Intelligent Transportation Systems, 23(4), 3878-3889.
- 单位：Xiamen University .
- 原文链接：https://ieeexplore.ieee.org/abstract/document/9707740
- 概述：本文根据参与者的历史轨迹，推测其轨迹，并采用了一种least-interrupt urban sensing strategy（最小干扰策略，可小幅度改变招募者轨迹），用以解决maximal weighted sensing paths (MWSP) problem最大化加权路段感知问题（路段存在权重）。
二、动机及创新点
动机：
过去的方法主要采用参与式方式进行，需要指导用户的移动轨迹，并且会对交通产生负担，机会式的方法不需要改变用户轨迹，且对交通负担较小。
主要贡献及创新点：
引入了最大加权路段感知，基于历史轨迹数据集对路段设置不同的权重，目标是最大化感知加权路径；框架包括车辆招募，候选路径计算和路径计算三部分，采用最少干扰策略，增加驾驶员参与感知的意愿度。
三、问题描述和方法论
地图使用G(V,E)表示，E为V->V的边，路的权重为w(e)。
路径可行：具有相同起点和终点的路径，可分为最短路径和可行路径。
$$ \left\{l \mid \operatorname{cost}(1 l) \leq(1+\tau) \cdot \text { co } s\left(l^{*}\right) \text { and } r \text { is covered by } l\right\} $$其中，$l^*$为最短路径，$l$为可行路径。
问题形式化：
其中，$P_r^T$为绕路集合，用于least-interrupt问题说明，解释了此问题为NP-hard问题。
四、算法设计
Crowdsourced Vehicular Sensing (CVS) framework
由于车辆中存在大量重叠和相似数据，通过扫描数据集，剔除冗余的数据分为以下三个步骤：
1)车辆招募：该系统招募一组车辆参与传感，同时给予一个成本预算。因此，路由子集，例如R⊆R，从路由集中选择。
首先对车辆和其最优路径（不包含可行路径）进行路径权重最大化。以选中车辆，该问题是一个ILP问题，可解决。
2)候选路径计算：对于每条路由，从所有可行路径集中只选择部分路径作为候选路径。对冗余和相似的路径进行修剪，以减小问题的大小；
3)路径计算：给定选定的路径及其可行的候选路径，用于求解：
有了车辆和候选路径集，问题规模大大减小，加入限制条件如：1.每辆车都应选择，2.每辆车仅可选择一条路径3.如果一条路径对于一辆车无论如何都会被选中，可直接加入无需计算，最后最大化权重即可。
$$
max{\sum_{1 \le i\le m}\ w\left(e_i\right)}\ast\ t_i
$$
五、实验部分
采用厦门5000个轨迹的起点终点作为数据点。
